package com.xxy.recursion;

/**
 * @author xxy
 * @create 2020 11 18 23:50
 * 迷宫问题：（回溯的思想）
 *
 */
public class MiGong {
    public static void main(String[] args) {
        //用二维数组来模拟迷宫
        int [][] map = new int[8][7];
        //墙用1表示
        for(int i =0 ;i<7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for(int i =0;i<8;i++){
            map[i][0] = 1;
            map[i][6] =1;
        }
        map[3][1] =1;
        map[3][2] = 1;
        //迷宫的结构
        System.out.println("没走之前");
        for(int i =0;i<8;i++){
            for(int j=0;j<7;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        setWay(map,1,1);
        System.out.println("走过之后");
        for(int i =0;i<8;i++){
            for(int j=0;j<7;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
    //找路

    /**
     * i,j表示开始的位置
     * 如果小球能到map[6][5],表示能走通
     * 约定：当map[i][j]为0，表示么有走过，1表示墙，2表示通过可以走，3，表示已经走过，但是走不通
     * 行走的方式：下，右，上，左
     *  map表示地图
     * i走的位置
     *  j走的位置
     * @return走的通返回true，否则返回false
     */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5]==2){
            return true;
        }else {
            if(map[i][j]==0){//如果当前这个点还没走过
                map[i][j]=2;//按照策略走，下 -右-上-左，假设当前节点走过
                if(setWay(map,i+1,j)){//往下
                    return true;
                }else if(setWay(map,i,j+1)){//往右
                    return true;
                }else if(setWay(map,i-1,j)){//往上
                    return true;
                }else if(setWay(map,i,j-1)){//往左
                    return true;
                }else {
                    map[i][j] =3;//走不通，死路
                    return false;
                }
            }else {
                return false;
            }
        }

    }
}
